#include <assert.h>
#include <string.h>
#include "ext2.h"
#include "ourhdr.h"

static int fd;			/* file descriptor of device */
static struct filsys_ext2 * e2fs;	/* pointer to struct filsys_ext2. 
									   We can get basic information about the filesystem */
static uint32_t next_available_block;	/* Used to mark where next available block is . */
static uint32_t next_available_inode_num;	/* Use to mark next available inode num is . */

static uint32_t alloc_file(int type, uint64_t size, const char* filename,uint32_t p_inode_num);
static void test_alloc_file();
static uint32_t alloc_inode_number();
static void write_continous_block_bitmap(uint32_t start, uint32_t end);
static void write_dir_entry(uint32_t pinode, uint32_t new_inode,uint32_t type, const char * filename);
static void clear_blocks(uint32_t start_block, uint32_t blocks_cnt);


/* Function: Calculate how many indirect blocks a large file needed.
 * The field i_block array in inode structure may point to some indirect blocks
 *
 * parms:
 * file_blocks : count of blocks file itself occupied.
 */
static uint32_t calcu_extra_blocks(uint32_t file_blocks){
	uint32_t extra_blocks = 0;
	if (file_blocks <= 12)
		extra_blocks = 0;
	else if (file_blocks <= 12 + BLK_SZ/4)
		extra_blocks = 1;
	else if (file_blocks <= 12 + BLK_SZ/4 + BLK_SZ/4*BLK_SZ/4)
		extra_blocks = 1 + 1 + (file_blocks - (12 + BLK_SZ/4) + BLK_SZ/4 - 1)/(BLK_SZ/4);
	else{
		uint32_t remained = file_blocks - (12 + BLK_SZ/4 + BLK_SZ/4*BLK_SZ/4);
		if(remained % (BLK_SZ/4*BLK_SZ/4) == 0)
			extra_blocks = 1 + (1+BLK_SZ) + 1 + (remained / (BLK_SZ/4*BLK_SZ/4)) * (1 + BLK_SZ/4);
		else {
			uint32_t indirect2 = remained / (BLK_SZ/4* BLK_SZ/4);
			remained = remained % (BLK_SZ/4*BLK_SZ/4);
			uint32_t indirect3_surplus = (remained + BLK_SZ - 1)/BLK_SZ;
			extra_blocks = 1 + (1+BLK_SZ) + 1 + indirect2 + 1 + (indirect2*BLK_SZ/4) + indirect3_surplus;
		}
	}
	return extra_blocks;
}

static void test_calcu_extra_blocks(){
	uint64_t test_array[] = {
		10,		16,		64,		1024,	2048,
		1<<20,	1<<21,	1<<25,	1<< 30, 1ul<<31,
		3ul<<30
	};
	for(int i = 0; i < sizeof(test_array)/sizeof(test_array[0]); i++){
		printf("%ld blocks need %ld extra blocks\n",
				test_array[i], calcu_extra_blocks(test_array[i]));
	}
}

/* Function: mark the corresponding inode bitmap bit of given inode number.
 * Parms:
 * inode_num : inode number.
 * e2fs : pointer of filesystem struct.
 */
static void mark_inode_bitmap(uint32_t inode_num, struct filsys_ext2* e2fs){
	inode_num--;
	uint32_t group_index = inode_num / INODS_PER_GRP;
	uint32_t inode_off = inode_num % INODS_PER_GRP;
	uint32_t byte_off = inode_off / 8;
	uint32_t bit_off = inode_off % 8;

	uint64_t write_pos = group_index * GRP_SZ + (2 + e2fs->group_desc_blocks) * BLK_SZ + byte_off;
	lseek(fd, write_pos, SEEK_SET);
	uint8_t tmp;
	read(fd, &tmp, sizeof(uint8_t));
	//assert((tmp & ~(1u << bit_off)) == 0);
	tmp |= (1u << bit_off);

	lseek(fd, write_pos, SEEK_SET);
	write(fd, &tmp, sizeof(tmp));

}



void pre_allocation_ext2(struct filsys_ext2* fs){
	e2fs = fs;
	next_available_block = 9;
	next_available_inode_num = 13;

	if( (fd = open(e2fs->device, O_RDWR)) < 0)
		err_sys("open error");
	printf("preallocate folders and files...\n");

	if(e2fs->total_size < MIN_DSK_SZ)
		err_quit("fail to preallocation.No enough disk space");
	/* calculate folders count needed and how many files in last folder */

	unsigned folders_cnt;
	unsigned last_folder_file_cnt;
	
	uint32_t available_blocks = e2fs->block_count - e2fs->group_count * e2fs->data_blk_offset;

	uint32_t extra_blocks = calcu_extra_blocks(VIDEO_FILE_BLKS);	/* inode indirect blocks */

#define 	blocks_pack_need  (VIDEOS_PER_PACK * (VIDEO_FILE_BLKS + extra_blocks) + INDEXS_PER_PACK * INDEX_FILE_BLKS + FOLDER_BLKS)
	folders_cnt = (available_blocks - ALLOC_INFO_FILE_BLKS + blocks_pack_need - 100)/ blocks_pack_need;
	last_folder_file_cnt = (available_blocks - (folders_cnt -1) * blocks_pack_need - FOLDER_BLKS - INDEXS_PER_PACK * INDEX_FILE_BLKS ) / (VIDEO_FILE_BLKS + extra_blocks);

	disp(folders_cnt);
	disp(last_folder_file_cnt);

#if 0
	test_alloc_file();
#endif

	/* alloc dirs */
	uint32_t inode_of_folder[folders_cnt];
	for(int i = 0; i < folders_cnt; i++){
		char folder_name[] = "folder  ";
		folder_name[6] = '0' + i / 10;
		folder_name[7] = '0' + i % 10;
		inode_of_folder[i] = alloc_file(EXT2_FT_DIR, BLK_SZ, folder_name, 2);
	}

	/* alloc alloc-info file */
	char file_name[] = "allocinf";
	alloc_file(EXT2_FT_REG_FILE, ALLOC_INFO_FILE_BLKS * BLK_SZ, file_name, 2);

	/* alloc index files in each dir */
	for(int i = 0; i < folders_cnt; i++){
		char file_name[] = "index ";
		for(int j = 0; j < INDEXS_PER_PACK; j++){
			file_name[5] = '0' + j;
			alloc_file(EXT2_FT_REG_FILE, INDEX_FILE_BLKS * BLK_SZ, file_name, inode_of_folder[i]);
		}
	}
	/* alloc video file in each dir */
	for(int i = 0; i < folders_cnt - 1; i++){
		for(int j = 0; j < VIDEOS_PER_PACK; j++){
			char file_name[] = "video  .mp4";
			file_name[5] = '0' + j / 10;
			file_name[6] = '0' + j % 10;
			alloc_file(EXT2_FT_REG_FILE, VIDEO_SZ, file_name, inode_of_folder[i]);
		}
	}
	for(int j = 0; j < last_folder_file_cnt; j++){
		char file_name[] = "video  .mp4";
		file_name[5] = '0' + j / 10;
		file_name[6] = '0' + j % 10;
		alloc_file(EXT2_FT_REG_FILE, VIDEO_SZ, file_name, inode_of_folder[folders_cnt - 1]);
	}


	close(fd);
}

static inline uint32_t avail_block_backward(uint32_t cur, uint32_t off){
	assert(cur % BLKS_PER_GRP >= e2fs->data_blk_offset);
	return (cur % BLKS_PER_GRP + off - e2fs->data_blk_offset) / (BLKS_PER_GRP - e2fs->data_blk_offset) * e2fs->data_blk_offset + off + cur;
}
static inline uint32_t get_next_block(uint32_t cur){
	return avail_block_backward(cur, 1);
}

/* p_inode_num : parent directory's inode number */
static uint32_t alloc_file(int type, uint64_t size, const char* filename,uint32_t p_inode_num){
	uint32_t file_blocks = (size + BLK_SZ - 1) / BLK_SZ;
	uint32_t old_next_available_block = next_available_block;
	/* allloc the inode number */

	uint32_t new_inode_num = alloc_inode_number();
	disp(new_inode_num);
	uint32_t group_index = next_available_block / BLKS_PER_GRP;

	/* fill the inode struct */
	time_t cur_time = time(0);
	struct ext2_inode new_inode = {
		.i_mode = ((type == EXT2_FT_DIR) ? EXT2_DIR_MODE : EXT2_REG_MODE) ,
		.i_size = size,
		.i_atime = cur_time,
		.i_ctime = cur_time,
		.i_mtime = cur_time,
		.i_links_count = ((type == EXT2_FT_DIR) ? 2 : 1),
		.i_blocks = file_blocks * (BLK_SZ / 512),
	};
	uint32_t indirect_blocks_start = avail_block_backward(next_available_block, file_blocks);
	uint32_t indirect_blocks_cur  = indirect_blocks_start;
	uint32_t content;

	/* fill the i_block array. Following steps are too long and redundent.*/
	if (file_blocks <= 12){
		for(int i = 0 ; i < file_blocks; i++){
			new_inode.i_block[i] = next_available_block;
			next_available_block = get_next_block(next_available_block);
		}
	} else if (file_blocks <= 12 + BLK_SZ/4){
		for(int i= 0; i < 12 ; i++){
			new_inode.i_block[i] = next_available_block;
			next_available_block = get_next_block(next_available_block);
		}
		new_inode.i_block[12] = indirect_blocks_cur;
		indirect_blocks_cur = get_next_block(indirect_blocks_cur);

		lseek(fd, BLK_SZ * new_inode.i_block[12], SEEK_SET);
		for(int j = 0; j < file_blocks - 12; j++){
			content = next_available_block;
			next_available_block = get_next_block(next_available_block);
			write(fd, &content, sizeof(content));
		}
	} else if (file_blocks <= 12 + BLK_SZ/4 + BLK_SZ/4*BLK_SZ/4){
		for(int i = 0; i < 12; i++){
			new_inode.i_block[i] = next_available_block;
			next_available_block = get_next_block(next_available_block);
		}
		new_inode.i_block[12] = indirect_blocks_cur;
		indirect_blocks_cur = get_next_block(indirect_blocks_cur);

		lseek(fd, BLK_SZ * new_inode.i_block[12], SEEK_SET);
		uint32_t content;
		for(int j = 0; j < BLK_SZ/4; j++){
			content = next_available_block;
			next_available_block = get_next_block(next_available_block);
			write(fd, &content, sizeof(content));
		}
		
		uint32_t index1 = 0;
		uint32_t cached_level1;
		uint32_t index2 = 0;
		uint32_t cached_level2;
		new_inode.i_block[13] = indirect_blocks_cur;
		indirect_blocks_cur = get_next_block(indirect_blocks_cur);

		for(int k = 0; k < file_blocks - 12 - BLK_SZ/4; k ++){
			if (k % (BLK_SZ/4) == 0){
				lseek(fd, new_inode.i_block[13] * BLK_SZ + index1, SEEK_SET);
				content = indirect_blocks_cur;
				indirect_blocks_cur = get_next_block(indirect_blocks_cur);
				write(fd, &content, sizeof(content));
				index1 += 4;
				lseek(fd, content * BLK_SZ, SEEK_SET);
			}
			content = next_available_block;
			next_available_block = get_next_block(next_available_block);
			write(fd, &content, sizeof(content));
		}

	} else {
		for(int i = 0; i < 12 ; i++){
			new_inode.i_block[i] = next_available_block;
			next_available_block = get_next_block(next_available_block);
		}
		new_inode.i_block[12] = indirect_blocks_cur;
		indirect_blocks_cur = next_available_block;

		lseek(fd, new_inode.i_block[12] * BLK_SZ, SEEK_SET);
		for(int i = 0; i < BLK_SZ/4; i++){
			content = next_available_block;
			next_available_block = get_next_block(next_available_block);
			write(fd, &content, sizeof(content));
		}

		int index1;
		new_inode.i_block[13] = indirect_blocks_cur;
		indirect_blocks_cur = get_next_block(indirect_blocks_cur);
		for(int i = 0; i < BLK_SZ/4*BLK_SZ/4; i++){
			if(i % (BLK_SZ/4) == 0){
				lseek(fd, new_inode.i_block[13]*BLK_SZ + index1, SEEK_SET);
				content = indirect_blocks_cur;
				indirect_blocks_cur = get_next_block(indirect_blocks_cur);
				write(fd, &content, sizeof(content));
				index1 += 4;
				lseek(fd, content*BLK_SZ, SEEK_SET);
			}
			content = next_available_block;
			next_available_block = get_next_block(next_available_block);
			write(fd, &content, sizeof(content));
		}
		index1 = 0;
		int index2 = 0;
		new_inode.i_block[14] = indirect_blocks_cur;
		indirect_blocks_cur = get_next_block(indirect_blocks_cur);

		for(int i = 0; i < BLK_SZ/4*BLK_SZ/4*BLK_SZ/4; i++){
			if((i % (BLK_SZ/4)) == 0){
				if((i % (BLK_SZ/4*BLK_SZ/4)) == 0){
					lseek(fd, new_inode.i_block[14]*BLK_SZ + index1, SEEK_SET);
					content = indirect_blocks_cur;
					indirect_blocks_cur = get_next_block(indirect_blocks_cur);
					write(fd, &content, sizeof(content));
					index1 += 4;
					index2 = 0;
					lseek(fd, content*BLK_SZ,SEEK_SET);
				}
				content = indirect_blocks_cur;
				indirect_blocks_cur = get_next_block(indirect_blocks_cur);
				write(fd, &content, sizeof(content));
				index2 += 4;
				lseek(fd, content*BLK_SZ,SEEK_SET);
			}
			content = next_available_block;
			next_available_block = get_next_block(next_available_block);
			write(fd, &content, sizeof(content));
		}
	}
	next_available_block = indirect_blocks_cur;

	/* write inode table */
	int32_t inode_offset = new_inode_num % INODS_PER_GRP - 1;
	assert(inode_offset >= 0);
	lseek(fd, group_index * GRP_SZ + offset_of_inode_table(e2fs) * BLK_SZ + inode_offset * EXT2_GOOD_OLD_INODE_SIZE, SEEK_SET);
	write(fd, &new_inode, sizeof(new_inode));
	
	/* write inode bitmap and blocks bitmap */
	mark_inode_bitmap(new_inode_num, e2fs);
	write_continous_block_bitmap(old_next_available_block, next_available_block);

	/* write parent dir's entry */
	write_dir_entry(p_inode_num, new_inode_num, type, filename);

	/* if type == dir, clear the file and write dir entry . and .. ; add links count of parent dir */
	if(type == EXT2_FT_DIR){
		if(new_inode.i_size <= BLK_SZ){
			clear_blocks(new_inode.i_block[0], 1);
		} else {
			err_quit("too large directory");
		}
		write_dir_entry(new_inode_num, new_inode_num, EXT2_FT_DIR, ".");
		write_dir_entry(new_inode_num, p_inode_num, EXT2_FT_DIR, "..");

		struct ext2_inode parent_inode;
		uint32_t parent_group_index = (p_inode_num - 1) / INODS_PER_GRP;
		uint32_t p_inode_offset = (p_inode_num - 1) % INODS_PER_GRP;
		lseek(fd, parent_group_index * GRP_SZ + offset_of_inode_table(e2fs) * BLK_SZ + p_inode_offset * EXT2_GOOD_OLD_INODE_SIZE, SEEK_SET);
		read(fd, &parent_inode, sizeof(parent_inode));
		parent_inode.i_links_count ++;
		lseek(fd, parent_group_index * GRP_SZ + offset_of_inode_table(e2fs) * BLK_SZ + p_inode_offset * EXT2_GOOD_OLD_INODE_SIZE, SEEK_SET);
		write(fd, &parent_inode, sizeof(parent_inode));
	
	}

	return new_inode_num;
	
}
static void write_dir_entry(uint32_t pinode_num, uint32_t new_inode,uint32_t type, const char * filename){
	uint32_t file_name_len = strlen(filename);
	struct ext2_dir_entry new_entry = {
		.inode = new_inode,
		.name_len = file_name_len,
		.rec_len = (file_name_len + 3) / 4 * 4 + 8,
		.file_type = type
	};
	strncpy(new_entry.name, filename, file_name_len);
	uint32_t parent_group = (pinode_num - 1) / INODS_PER_GRP;
	uint32_t offset = (pinode_num - 1) % INODS_PER_GRP;
	struct ext2_inode parent_inode;
	lseek(fd, parent_group * GRP_SZ + offset_of_inode_table(e2fs) * BLK_SZ + offset * EXT2_GOOD_OLD_INODE_SIZE, SEEK_SET);
	read(fd, &parent_inode, sizeof(parent_inode));
	/* directory entries mostly occupy only one block. TODO: take all situations into account */
	uint32_t first_block_id = parent_inode.i_block[0];
	lseek(fd, first_block_id * BLK_SZ, SEEK_SET);
	uint32_t content;
	uint32_t index = 0;
	do{
		read(fd, &content, sizeof(content));
		index ++;
	}while(content);
	lseek(fd, first_block_id * BLK_SZ + sizeof(content) * (index - 1) , SEEK_SET);
	write(fd, &new_entry, new_entry.rec_len);
}

static void test_alloc_file(){
	alloc_file(EXT2_FT_REG_FILE, VIDEO_SZ, "test_long_name_file", 2);
	alloc_file(EXT2_FT_DIR,BLK_SZ, "test_folder", 2);
	alloc_file(EXT2_FT_DIR,10 * BLK_SZ, "test_file", 2);
}

static uint32_t alloc_inode_number(){
	uint32_t group_index = next_available_block / BLKS_PER_GRP;
	uint32_t new_inode_num = group_index * INODS_PER_GRP + 1;
	if(new_inode_num > next_available_inode_num){
		next_available_inode_num = new_inode_num;
	}
	new_inode_num = next_available_inode_num;
	next_available_inode_num ++;

	return new_inode_num;

}
static uint8_t table[8] = {0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f};
static void write_continous_block_bitmap(uint32_t start, uint32_t end){
	uint32_t start_group = start / BLKS_PER_GRP;
	uint32_t end_group = end/ BLKS_PER_GRP;

	for(int i = start_group; i < end_group; i++){
		uint32_t content = 0xffffffff;
		lseek(fd, i * GRP_SZ + offset_of_block_bitmap(e2fs) * BLK_SZ, SEEK_SET);
		for(int j = 0; j < BLK_SZ/4; j++){
			write(fd, &content, sizeof(content));
		}
	}
	uint32_t surplus = end % BLKS_PER_GRP;
	uint32_t offset = surplus / 8;
	uint32_t surplus_bit = surplus % 8;

	uint8_t content = 0xff;
	lseek(fd, end_group * GRP_SZ + offset_of_block_bitmap(e2fs) * BLK_SZ, SEEK_SET);
	for(int i = 0; i < offset; i++){
		write(fd, &content, sizeof(content));
	}
	write(fd, &table[surplus_bit], sizeof(table[surplus_bit]));


}

static void write_by_inode(uint32_t inode_num, uint64_t offset, void* buf, size_t size){
	uint32_t group_index = (inode_num - 1) / INODS_PER_GRP;
	uint32_t inum_offset = (inode_num - 1) % INODS_PER_GRP;

	/* read the inode */
	struct ext2_inode temp_inode;
	lseek(fd, group_index * GRP_SZ + offset_of_inode_table(e2fs) * BLK_SZ + inum_offset * EXT2_GOOD_OLD_INODE_SIZE,SEEK_SET);
	read(fd, &temp_inode, sizeof(temp_inode));

	/* check the size */
	if(offset + size > temp_inode.i_size){
		fprintf(stderr, "overflow when write_by_inode\n");
		exit(1);
	}

	/* seek the write_pos and write contents */
	// TODO

}

static void clear_blocks(uint32_t start_block, uint32_t blocks_cnt){
	char* buf;
	if ((buf = (char*) malloc(BLK_SZ)) == 0)
		err_quit("fail to malloc in clear_blocks function");
	memset(buf, 0, BLK_SZ);
	lseek(fd, start_block * BLK_SZ,SEEK_SET);
	for(unsigned int i = 0; i < blocks_cnt; i++)
		write(fd, buf, BLK_SZ);
	free(buf);
}
